Isotemporal classes of diasters, beachballs, and daisies

摘要

If the vertices composing a network interact at distinct time points, thetemporal ordering of these interactions and the network's graph structure aresufficient to convey the routes by which information can flow in the network.Two networks with real-valued edge labels are temporally isomorphic if thereexists a graph isomorphism f:N->M that preserves temporal paths - paths inwhich sequential edge labels are strictly increasing. An equivalence class oftemporally ismorphic networks is known as an isotemporal class. Methods todetermine the number of isotemporal classes of a particular graph structureN(G) are non-obvious, and refractory to traditional techniques such as P\'olyaenumeration (P\'olya, 1937). Here, I present a simple formula for the number ofisotemporal classes of diasters, graphs composed of a vertex of degree a+1connected to a vertex of degree b+1, with all other vertices of degree 1(denoted D(a,b)). In particular, N(D(a,b)))=ab+a+b+1 if a is not equal to b,and N(D(a,a)))=(1/2) (a^2+3a+2) otherwise. This formula is then extended tofive additional types of pseudograph by application of a theorem that statesN(G) is preserved between two graph types if edge adjacencies and automorphismsare preserved, and provided that any two networks are members of the sameisotemporal class if and only if they are isomorphic by transpositions ofsequential edge labels on non-adjacent edges.